package sort;

import java.util.Stack;

public class QuickSortNor {
    public static int holePartition(int[] arr,int left,int right){
        int tmp = arr[left];
        while(left < right){
            while(left < right && arr[right] >= tmp){
                right--;
            }
            arr[left] = arr[right];
            while(left < right && arr[left] <= tmp){
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = tmp;
        return left;
    }
    public static void quickSort(int[] arr){
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = arr.length-1;
        int pivot = holePartition(arr,left,right);
        if(left < pivot-1){
            stack.push(left);
            stack.push(pivot-1);
        }
        if(pivot+1 < right){
            stack.push(pivot+1);
            stack.push(right);
        }
        while(!stack.isEmpty()){
            right = stack.pop();
            left = stack.pop();
            pivot = holePartition(arr,left,right);
            if(left < pivot-1){
                stack.push(left);
                stack.push(pivot-1);
            }
            if(pivot+1 < right){
                stack.push(pivot+1);
                stack.push(right);
            }

        }
    }

    public static void main(String[] args) {
        int[] arr = {1,5,3,5,71,34,56,43,9,12,15};
        quickSort(arr);
        for(int i:arr){
            System.out.print(i+" ");
        }
    }
}
